package leecode

func isPalindrome234(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}

	// 找到链表中点
	slow, fast := head, head
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	// 反转后半部分链表
	reversed := reverseListLCR(slow.Next)
	slow.Next = nil // 断开前后两部分链表的连接

	// 比较前后两部分链表
	p1, p2 := head, reversed
	for p1 != nil && p2 != nil {
		if p1.Val != p2.Val {
			return false
		}
		p1 = p1.Next
		p2 = p2.Next
	}

	return true
}

// 反转链表
func reverseListLCR(head *ListNode) *ListNode {
	var prev *ListNode
	curr := head
	for curr != nil {
		next := curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	return prev
}
